public class LeetCode62 {
    public int uniquePaths(int m, int n) {
        // 创建一个二维数组 dp，大小为 m x n，用于存储到达每个格子的路径数目。
        int[][] dp = new int[m][n];
        // 初始化 dp 表，第一行和第一列都为 1
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;

        // 填充 dp 表：对于每一个非边界元素 (i, j)，其值等于上方元素 (i-1, j) 和左侧元素 (i, j-1) 的和。
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        // 返回右下角元素 dp[m-1][n-1]，即为从左上角到右下角的不同路径数量。
        return dp[m - 1][n - 1];
    }
}
